package com.sxu.greedy.day5;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 俄罗斯套娃信封问题
 *  重写排序 + 贪心 + 二分
 */
public class Test25_2 {
    public int maxEnvelopes(int[][] envelopes) {
        // 重写排序
        Arrays.sort(envelopes, (v1,v2)->{
            return v1[0] != v2[0] ? v1[0] - v2[0] : v2[1] - v1[1];
        });

        // 贪心 + 二分
        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(envelopes[0][1]);

        for(int i=1;i<envelopes.length;i++){
            int b = envelopes[i][1];
            if(b > ret.get(ret.size()-1)){
                ret.add(b);
            } else {
                int left = 0;
                int right = ret.size()-1;
                while(left < right){
                    int mid = (left+right)/2;
                    if(ret.get(mid) >= b){
                        right = mid;
                    } else {
                        left = mid+1;
                    }
                }
                ret.set(left,b);
            }
        }
        return ret.size();
    }
}
